//
// Description: 二叉树序列互求
// Created by Loading on 2021/5/12.
//

// 根据二叉树的前序和中序遍历序列，求得其后序遍历序列
// 根据二叉树的中序和后序遍历序列，求得其前序遍历序列
/* 根据二叉树的前序和后序遍历序列，无法求得唯一中序序列 */

#include <bits/stdc++.h>

using namespace std;

/* 根据前序中序求后序 */
void findPostorderInternal(vector<int> &preorder, vector<int> &inorder, vector<int> &postorder) {
    if (preorder.empty() || inorder.empty()) {
        return;
    }
    //寻找根节点在中序序列中的位置以及左子树长度
    auto it = find(inorder.begin(), inorder.end(), preorder[0]);
    int len_left = distance(inorder.begin(), it);
    //左子树
    vector<int> v1(preorder.begin() + 1, preorder.begin() + 1 + len_left);
    vector<int> v2(inorder.begin(), inorder.begin() + len_left);
    //右子树
    vector<int> v3(preorder.begin() + 1 + len_left, preorder.end());
    vector<int> v4(inorder.begin() + len_left + 1, inorder.end());

    //左子树求后序
    findPostorderInternal(v1, v2, postorder);
    //右子树求后序
    findPostorderInternal(v3, v4, postorder);
    //左右子树分别计算完成，加入根节点
    postorder.emplace_back(*it);
}

vector<int> findPostorder(vector<int> &preorder, vector<int> &inorder) {
    vector<int> postorder;
    findPostorderInternal(preorder, inorder, postorder);

    return postorder;
}

/* 根据中序后序求前序 */
void findPreorderInternal(vector<int> &inorder, vector<int> &postorder, vector<int> &preorder) {
    if (inorder.empty() || postorder.empty()) {
        return;
    }
    //寻找根节点在中序序列中的位置以及左子树长度
    auto it = find(inorder.begin(), inorder.end(), postorder[postorder.size() - 1]);
    int len_left = distance(inorder.begin(), it);
    //左子树
    vector<int> v1(inorder.begin(), inorder.begin() + len_left);
    vector<int> v2(postorder.begin(), postorder.begin() + len_left);
    //右子树
    vector<int> v3(inorder.begin() + len_left + 1, inorder.end());
    vector<int> v4(postorder.begin() + len_left, postorder.end() - 1);

    //加入根节点
    preorder.emplace_back(*it);
    //左子树求前序
    findPreorderInternal(v1, v2, preorder);
    //右子树求前序
    findPreorderInternal(v3, v4, preorder);
}

vector<int> findPreorder(vector<int> &inorder, vector<int> &postorder) {
    vector<int> preorder;
    findPreorderInternal(inorder, postorder, preorder);

    return preorder;
}

int main() {
    //求后序
    vector<int> preorder = {1, 2, 3, 4, 5};
    vector<int> inorder = {2, 1, 4, 3, 5};
    vector<int> postorder = findPostorder(preorder, inorder);
    for (const auto &x : postorder) {
        cout << x << " ";
    }
    cout << endl;

    //求前序
    vector<int> inorder_ = {2, 1, 4, 3, 5};
    vector<int> postorder_ = {2, 4, 5, 3, 1};
    vector<int> preorder_ = findPreorder(inorder_, postorder_);
    for (const auto &x : preorder_) {
        cout << x << " ";
    }
    cout << endl;
}